package _02_第二季._01_排序;

public class HeapSort03<E extends Comparable<E>> extends Sort<E> {
    private int heapSize; //堆元素的个数
    @Override
    protected void sort() {
        heapSize = array.length;
        for(int i=(heapSize >> 1) - 1;i>=0;--i){
            siftDown(i);
        }
        while(heapSize>1){
            swap(0,--heapSize);
            siftDown(0);
        }
    }

    private void siftDown(int index){
        E element = array[index];
        int half = heapSize >> 1;
        while(index<half){
            int leftChildIndex = (index << 1) + 1;
            E leftChildElement = array[leftChildIndex];
            int rightChildIndex = leftChildIndex + 1;
            if(rightChildIndex<heapSize && cmp(leftChildElement,array[rightChildIndex])<0){
                leftChildElement = array[leftChildIndex = rightChildIndex];
            }
            if(cmp(element,leftChildElement)>=0) break;

            array[index] = leftChildElement;
            index = leftChildIndex;
        }
        array[index] = element;
    }
}
